package Greedy.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1. 问题描述
 *      给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
 *      如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
 *      与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，
 *      它可以通过从数组中分离一些（也可能不分离）元素得到。
 *      注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
 *
 * 2. 算法分析
 *      算法分析
 *          典型的贪心
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 非递增顺序的最小子序列 {
    public static void main(String[] args) {

    }

    /**
     *  模拟法 (暴力法)   时间复杂度为O(n^2)  不推荐，思路简单而已，代码的效率非常低
     *  将数组排序之后 从后往前遍历，判断当前元素添加到list之后能否满足条件
     * @param nums
     * @return
     */
    public List<Integer> minSubsequence1(int[] nums) {
        List<Integer> ans = new ArrayList<>(); // 存放结果
        Arrays.sort(nums); // 按照递增的顺序
        int anssum = 0; // 记录ans中的元素和
        for(int i = nums.length-1; i >= 0; i--) { // 从元素大的下进行扫描
            // 贪心的第一条件：返回的子序列的长度进可能的小，尽量将大的元素放置到ans中
            // 判断如果将当前元素放置到ans中之后是否满足条件
            anssum += nums[i];
            ans.add(nums[i]);
            int sum = 0;
            for(int j = i-1; j >=0; j--) {
                sum += nums[j];
            }
            if(anssum > sum) {
                return ans;
            }
        }
        return null;
    }

    /**
     * 所求的子序列一定出现在中间nums[len/2-1:len]之间，所以我们没有必须
     * 不对。实际上没有优化，因为上述一旦满足直接return了，并不会继续for，所以上述代码和这里的代码效率基本上一样
     * @param nums
     * @return
     */
    public List<Integer> minSubsequence2(int[] nums) {
        List<Integer> ans = new ArrayList<>(); // 存放结果
        Arrays.sort(nums); // 升序
        int ansSum = 0;
        for(int i = nums.length-1; i >= nums.length / 2 - 1; i--) {
            ansSum += nums[i];
            ans.add(nums[i]);
            int temp = 0;
            for(int j = i-1; j >= 0; j--) {
                temp += nums[j];
            }
            if(temp < ansSum) {
                return ans;
            }
        }
        return null;
    }

    /**
     *  通过线性扫描求出数组的总和，然后排序，之后在从尾部到头部扫描，知道list中的和大于数组的总和
     * @param nums
     * @return
     */
    public List<Integer> minSubsequence3(int[] nums) {
        List<Integer> ans = new ArrayList<>(); // 存放结果
        Arrays.sort(nums); // 升序
        int sum = nums[0]; // 记录序列的总和
        for(int i = 1; i < nums.length; i++) {
            sum += nums[i];
        }
        int anssum = 0;
        for(int i = nums.length-1; i >= nums.length/2-1; i--) {
            if(anssum <= sum) {
                ans.add(nums[i]);
                sum -= nums[i];
                anssum += nums[i];
            }
        }
        return ans;
    }

}
